package one.chapter_2;

/**
 * 自底向上的归并排序
 * 思想：
 * 把一个长度为N的数组，看成是N个数组，每个数组长度为1，
 * 然后将他们两两合并，之后四四合并，一直下去直到结束。
 *
 * sz=2
 * lo  mid=lo+sz-1   hi=lo+sz+sz-1
 *   -- -- -- -- -- -- -- --
 *   两两合并
 *
 *   ---- ---- ----
 *
 */
public class MergeBUSort extends AbstractSort {


    private Comparable [] aux;//辅助数组
    protected void sort(Comparable[] a) {
        int N=a.length;
        aux=new Comparable[N];
       for (int sz=1;sz<N;sz=sz+sz){
           for (int lo=0;lo<N-sz;lo=lo+sz+sz){
               merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
           }
       }
    }

    private void merge(Comparable[] a, int lo, int mid, int hi) {
        for (int k=lo;k<=hi;k++){
            aux[k]=a[k];
        }
        int i=lo;
        int j=mid+1;
        for (int k=lo;k<=hi;k++){
            if (i>mid){//左半侧指针位置超过一半，说明左右两侧比较结束了，右侧还有剩余元素
                a[k]=aux[j++];
            }else if (j>hi){//右半侧指针位置超出数组长度，说明左右两侧比较结束了，左侧还有剩余元素
                a[k]=aux[i++];
            }else if (less(aux[j],aux[i])){//左右两侧对应元素进行比较
                a[k]=aux[j++];
            }else {
                a[k]=aux[i++];
            }
        }
    }
}
